
//2389.和有限的最长子序列
class Solution {
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
        //前缀和+二分查找
        //先对数组进行排序
        int n=nums.size(),m=queries.size();
        sort(nums.begin(),nums.end());
        vector<long> sum(n);  //用sum[i]来记录前i个值的总和

        sum[0]=nums[0];
        for(int i=1;i<n;i++) sum[i]=sum[i-1]+nums[i];

        //遍历数组，使用二分查找出第一个大于queries的位置
        vector<int> ret(m);
        for(int i=0;i<m;i++)
        {
            int len=upper_bound(sum.begin(),sum.end(),queries[i])-sum.begin();
            ret[i]=len;
        }
        return ret;
    }
};